home *** CD-ROM | disk | FTP | other *** search
/ Aminet 28 / Aminet 28 (1998)(GTI - Schatztruhe)[!][Dec 1998].iso / Aminet / game / board / Crafty-15.19.lha / crafty-15.19 / src / searchr.c < prev    next >
C/C++ Source or Header  |  1998-09-13  |  12KB  |  299 lines
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include "chess.h"
  5. #include "data.h"
  6. #include "epdglue.h"
  7.  
  8. /* modified 06/05/98 */
  9. /*
  10. ********************************************************************************
  11. *                                                                              *
  12. *   SearchRoot() is the recursive routine used to implement the alpha/beta     *
  13. *   negamax search (similar to minimax but simpler to code.)  SearchRoot() is  *
  14. *   only called when ply=1.  it is somewhat different from Search() in that    *
  15. *   some things (null move search, hash lookup, etc.) are not useful at the    *
  16. *   root of the tree.  SearchRoot() calls Search() to search any positions     *
  17. *   that are below ply=1.                                                      *
  18. *                                                                              *
  19. ********************************************************************************
  20. */
  21. int SearchRoot(TREE *tree, int alpha, int beta, int wtm, int depth) {
  22.   register int first_move=1;
  23.   register int initial_alpha, value;
  24.   register int extensions, begin_root_nodes;
  25. /*
  26.  ----------------------------------------------------------
  27. |                                                          |
  28. |   initialize.  set NextMove() status to 0 so it will     |
  29. |   know what has to be done.                              |
  30. |                                                          |
  31.  ----------------------------------------------------------
  32. */
  33.   tree->in_check[2]=0;
  34.   tree->extended_reason[2]=no_extension;
  35.   initial_alpha=alpha;
  36.   RepetitionCheck(tree,1,wtm);
  37.   tree->in_check[1]=Check(wtm);
  38.   tree->next_status[1].phase=ROOT_MOVES;
  39. /*
  40.  ----------------------------------------------------------
  41. |                                                          |
  42. |   now iterate through the move list and search the       |
  43. |   resulting positions.  note that Search() culls any     |
  44. |   move that is not legal by using Check().  the special  |
  45. |   case is that we must find one legal move to search to  |
  46. |   confirm that it's not a mate or draw.                  |
  47. |                                                          |
  48.  ----------------------------------------------------------
  49. */
  50.   while ((tree->current_phase[1]=NextRootMove(tree,wtm))) {
  51.     tree->extended_reason[1]=0;
  52. #if !defined(FAST)
  53.     if (1 <= trace_level)
  54.       SearchTrace(tree,1,depth,wtm,alpha,beta,"SearchRoot",tree->current_phase[1]);
  55. #endif
  56. /*
  57.  ----------------------------------------------------------
  58. |                                                          |
  59. |   if we push a pawn to the 7th rank, we need to look     |
  60. |   deeper to see if it can promote.                       |
  61. |                                                          |
  62.  ----------------------------------------------------------
  63. */
  64.     extensions=-60;
  65.     if (Piece(tree->current_move[1])==pawn &&
  66.         ((wtm && To(tree->current_move[1]) > H5 && TotalBlackPieces<16 &&
  67.          !And(mask_pawn_passed_w[To(tree->current_move[1])],BlackPawns)) ||
  68.         (!wtm && To(tree->current_move[1]) < A4 && TotalWhitePieces<16 &&
  69.          !And(mask_pawn_passed_b[To(tree->current_move[1])],WhitePawns)) ||
  70.         push_extensions[To(tree->current_move[1])]) &&
  71.         Swap(tree,From(tree->current_move[1]),To(tree->current_move[1]),wtm) >= 0) {
  72.       tree->extended_reason[1]|=passed_pawn_extension;
  73.       tree->passed_pawn_extensions_done++;
  74.       extensions+=pushpp_depth;
  75.     }
  76. /*
  77.  ----------------------------------------------------------
  78. |                                                          |
  79. |   now make the move and search the resulting position.   |
  80. |                                                          |
  81.  ----------------------------------------------------------
  82. */
  83.     MakeMove(tree,1,tree->current_move[1],wtm);
  84. /*
  85.  ----------------------------------------------------------
  86. |                                                          |
  87. |   if the move to be made checks the opponent, then we    |
  88. |   need to remember that he's in check and also extend    |
  89. |   the depth by one ply for him to get out.               |
  90. |                                                          |
  91.  ----------------------------------------------------------
  92. */
  93.     if (Check(ChangeSide(wtm))) {
  94.       tree->in_check[2]=1;
  95.       tree->extended_reason[2]=check_extension;
  96.       tree->check_extensions_done++;
  97.       extensions+=incheck_depth;
  98.     }
  99.     else {
  100.       tree->in_check[2]=0;
  101.       tree->extended_reason[2]=no_extension;
  102.     }
  103. /*
  104.  ----------------------------------------------------------
  105. |                                                          |
  106. |   now call Search to produce a value for this move.      |
  107. |                                                          |
  108.  ----------------------------------------------------------
  109. */
  110.     begin_root_nodes=tree->nodes_searched;
  111.     extensions=Min(extensions,0);
  112.     if (first_move) {
  113.       value=-ABSearch(tree,-beta,-alpha,ChangeSide(wtm),
  114.                       depth+extensions,2,DO_NULL);
  115.       if (abort_search) {
  116.         UnMakeMove(tree,1,tree->current_move[1],wtm);
  117.         return(alpha);
  118.       }
  119.       first_move=0;
  120.     }
  121.     else {
  122.       value=-ABSearch(tree,-alpha-1,-alpha,ChangeSide(wtm),
  123.                       depth+extensions,2,DO_NULL);
  124.       if (abort_search) {
  125.         UnMakeMove(tree,1,tree->current_move[1],wtm);
  126.         return(alpha);
  127.       }
  128.       if ((value > alpha) && (value < beta)) {
  129.         value=-ABSearch(tree,-beta,-alpha,ChangeSide(wtm),
  130.                         depth+extensions,2,DO_NULL);
  131.         if (abort_search) {
  132.           UnMakeMove(tree,1,tree->current_move[1],wtm);
  133.           return(alpha);
  134.         }
  135.       }
  136.     }
  137.     tree->root_nodes[root_move]=tree->nodes_searched-begin_root_nodes;
  138.     if (value > alpha) {
  139.       SearchOutput(tree,value,beta);
  140.       if(value >= beta) {
  141.         History(tree,1,depth,wtm,tree->current_move[1]);
  142.         UnMakeMove(tree,1,tree->current_move[1],wtm);
  143.         StoreRefutation(tree,1,depth,wtm,value,0);
  144.         return(value);
  145.       }
  146.       alpha=value;
  147.       root_value=alpha;
  148.       beta=alpha+30;
  149.       root_beta=beta;
  150.     }
  151.     UnMakeMove(tree,1,tree->current_move[1],wtm);
  152.   }
  153. /*
  154.  ----------------------------------------------------------
  155. |                                                          |
  156. |   all moves have been searched.  if none were legal,     |
  157. |   return either MATE or DRAW depending on whether the    |
  158. |   side to move is in check or not.                       |
  159. |                                                          |
  160.  ----------------------------------------------------------
  161. */
  162.   if (abort_search) return(0);
  163.   if (first_move == 1) {
  164.     value=(Check(wtm)) ? -(MATE-1) : DrawScore(root_wtm==wtm);
  165.     if (value >=alpha && value <beta) {
  166.       SavePVS(tree,1,value,0);
  167. #if !defined(FAST)
  168.       if (1 <= trace_level) printf("Search() no moves!  ply=1\n");
  169. #endif
  170.     }
  171.     return(value);
  172.   }
  173.   else {
  174.     if (alpha != initial_alpha) {
  175.       memcpy(&tree->pv[0].path[1],&tree->pv[1].path[1],(tree->pv[1].path_length)*4);
  176.       memcpy(&tree->pv[0].path_hashed,&tree->pv[1].path_hashed,3);
  177.       History(tree,1,depth,wtm,tree->pv[1].path[1]);
  178.     }
  179.     StoreBest(tree,1,depth,wtm,alpha,initial_alpha,0);
  180.     return(alpha);
  181.   }
  182. }
  183.  
  184. /* modified 03/11/98 */
  185. /*
  186. ********************************************************************************
  187. *                                                                              *
  188. *   SearchOutput() is used to print the principal variation whenever it        *
  189. *   changes.  one additional feature is that SearchOutput() will try to do     *
  190. *   something about variations truncated by the transposition table.  if the   *
  191. *   variation was cut short by a transposition table hit, then we can make the *
  192. *   last move, add it to the end of the variation and extend the depth of the  *
  193. *   variation to cover it.                                                     *
  194. *                                                                              *
  195. ********************************************************************************
  196. */
  197. void SearchOutput(TREE *tree, int value, in